package bin_tree.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 后序 + 中序
 * @author yuisama
 * @date 2021/12/08 20:05
 **/
public class Num106 {
    // 存储中序遍历的对应的值和索引
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 将后序遍历结果反转
        int[] preOrder = reverse(inorder,postorder);
        return buildTreeInternal(preOrder,inorder,0,inorder.length);
    }
    int index = 0;
    public TreeNode buildTreeInternal(int[] preOrder,int[] inOrder,int left,int right) {
        if(left >= right) {
            return null;
        }
        if (index >= preOrder.length) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[index]);
        index ++;
        int pos = map.get(root.val);
        root.right = buildTreeInternal(preOrder,inOrder,pos + 1,right);
        root.left = buildTreeInternal(preOrder,inOrder,left,pos);
        return root;
    }

    private int[] reverse(int[] inorder,int[] postorder) {
        int[] ret = new int[postorder.length];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = postorder[ret.length - 1 - i];
        }
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return ret;
    }
}